#include "..\include\Graph.h"

Graph::Graph():Numiterator(0),maxflow(0)
{
    //ctor
}

Graph::~Graph()
{
    for( int i=0;i<Nodenum;i++)
    {
        delete[] GraphCapFlow[i];
        delete[] ReGraphCapFlow[i];
    }

    delete[] GraphCapFlow;
    delete[] ReGraphCapFlow;
    for(int j =0;j<Nodenum;j++)
    {
        node_t* pnode;
        while(pGraphArray[j].next != NULL)
        {
            pnode = pGraphArray[j].next;
            pGraphArray[j].next = pnode->next;
            delete pnode;
        }
    }
    delete[] pGraphArray;
    for(int j =0;j<Nodenum;j++)
    {
        node_t* pnode;
        while(pReGraphArray[j].next != NULL)
        {
            pnode = pReGraphArray[j].next;
            pReGraphArray[j].next = pnode->next;
            delete pnode;
        }
    }
    delete[] pReGraphArray;
}

void Graph::ReadGraph()
{
    FILE * is = fopen( "input.txt", "r" );
	if( is == NULL )
	{
		return;
	}
	int inum = 0;
	char line[MAXLINE];
	int checking,init, dest, cap;
	while(!feof(is)) //when the file ends, feof return non-zero
    {
        if(fgets(line,  MAXLINE, is) == NULL) break;
        char* str = strtok(line," ");
        switch (inum){
            case 0:
                Nodenum = atoi(str);
                str = strtok(NULL," ");
                Edgenum = atoi(str);
                GraphCapFlow = new CapAndFlow*[Nodenum];
                ReGraphCapFlow = new int*[Nodenum];
                pGraphArray = new node_t[Nodenum];
                pReGraphArray = new node_t[Nodenum];
                for(int i = 0; i<Nodenum;i++)
                {
                    GraphCapFlow[i]=new CapAndFlow[Nodenum];
                    ReGraphCapFlow[i]=new int[Nodenum];
                }
                for(int i = 0; i<Nodenum;i++)
                    for(int j = 0; j<Nodenum;j++)
                {
                    GraphCapFlow[i][j].cap = -1;
                    GraphCapFlow[i][j].flow = 0;
                    ReGraphCapFlow[i][j] = -1;
                }
                break;

            case 1:
                Source = atoi(str)-1;
                str = strtok(NULL," ");
                Sink = atoi(str)-1;
                str = strtok(NULL," ");
                checking = atoi(str);
                if(checking != Sink-Source)
                    return;
                break;
            default:
                init = atoi(str);
                str = strtok(NULL," ");
                dest = atoi(str);
                str = strtok(NULL," ");
                cap = atoi(str);
                init--;
                dest--;
                //construct the Graph: adjacency List
                node_t* pIndex = pGraphArray+ init;
                pIndex->i = init;
                node_t* pNode = new node_t;
                pNode->i = dest;
                pNode->next = pIndex->next;
                pIndex->next = pNode;
                //2.construct the cap and flow Matrix
                GraphCapFlow[init][dest].cap = cap;
                GraphCapFlow[init][dest].flow = 0;

                //coustruct the Residual Graph
                node_t* pReIndex = pReGraphArray + init;
                pReIndex->i= init;
                node_t* pReNode = new node_t;
                pReNode->i = dest;
                pReNode->next = pReIndex->next;
                pReIndex->next = pReNode;
                ReGraphCapFlow[init][dest] = cap;

                //cout<<"init:"<<init<<"   "<<"dest:"<<dest<<"    "<<"cap:"<<cap<<endl;
                break;

        }
        inum++;
    }

    outfile.open("output.txt");

    #ifdef debug
    for(int i = 0; i< Nodenum; i++){
        for(int j = 0; j<Nodenum; j++)
        {
        cout<<"("<<GraphCapFlow[i][j].cap<<","<<GraphCapFlow[i][j].flow<<")"<<": "<<ReGraphCapFlow[i][j]<<"  ";
        }
        cout<<endl;
    }

    #endif // debug
}

bool Graph::IsAugPath()
{
    //using Breath First Search Algorithm
    int* NodeIndex = new int[Nodenum];
    int* PaNode = new int[Nodenum];
    for(int j = 0;j<Nodenum; j++)
    {
        NodeIndex[j] = 0;
        PaNode[j] = -1; //save the parent Node
    }
    queue<int> nodequeue;
    node_t anode; //= pReGraphArray[0];
    nodequeue.push(0);
    NodeIndex[0] = 1;
    int n = Sink;
    //AugPath.push_back(n);
    while(!nodequeue.empty())
    {
        int nIndex = nodequeue.front();
        nodequeue.pop();
        anode = pReGraphArray[nIndex];
        while(anode.next != NULL )
        {
            if(NodeIndex[anode.next->i] == 1)
            {
                anode = *(anode.next);
                continue;
            }
            if(ReGraphCapFlow[pReGraphArray[nIndex].i][anode.next->i] == 0)
            {
                anode = *(anode.next);
                continue;
            }
            nodequeue.push(anode.next->i);
            NodeIndex[anode.next->i] = 1;
            PaNode[anode.next->i] = pReGraphArray[nIndex].i;
            if(anode.next->i == n)
            {
                AugPath.clear();
                while(n != Source)
                {
                    AugPath.push_front(n);
                    n = PaNode[n];
                }
                AugPath.push_front(Source);
                Numiterator++;
                delete[] NodeIndex;
                delete[] PaNode;
                outfile<<"The augment path at iteration "<<Numiterator<<" is:"<<endl;
                for(list<int>::iterator j = AugPath.begin();j != AugPath.end();++j)
                    outfile<<*j+1<<"    ";
                outfile<<endl;

                #ifdef debug
                for(list<int>::iterator j = AugPath.begin();j != AugPath.end();++j)
                {
                    int n = *j;
                    cout<<n+1<<endl;
                }

                #endif // debug
                return true;
            }
            anode = *(anode.next);
        }

    }
    delete[] NodeIndex;
    delete[] PaNode;
    return 0;
//    int n;
//    AugPath.push_back(anode.next->i);
//    n = PaNode[anode.next->i];
//    AugPath.push_back(PaNode[n])
//    while()
//    {
//        AugPath.push_back(PaNode[anode.next->i]);
//    }



}


void Graph::UpdateFlow()
{
    //caculate the bottleneck
    int n = AugPath.size();
//    int* nArray = new int[n];
    if(n>2)
    {
        list<int>::iterator j = AugPath.begin();
        int pre, next;
        pre = AugPath.front();
        next = *(++j);
        bottleneck = ReGraphCapFlow[pre][next];
        for(;j != AugPath.end();j++)
        {
            //pre = *(j++);
            next = *j;
            bottleneck = bottleneck < ReGraphCapFlow[pre][next] ? bottleneck : ReGraphCapFlow[pre][next];
            pre = next;
        }
        maxflow += bottleneck;
//        pre = *(j++);
//        next = *j;
//        bottleneck = bottleneck < ReGraphCapFlow[pre][next] ? bottleneck : ReGraphCapFlow[pre][next];
        //adjuct the flow of Graph
        j = AugPath.begin();
        pre = AugPath.front();
        ++j;
//        if(GraphCapFlow[pre][next].cap == -1)
//            GraphCapFlow[pre][next].flow = GraphCapFlow[pre][next].flow - bottleneck;
//        else
//            GraphCapFlow[pre][next].flow = GraphCapFlow[pre][next].flow + bottleneck;
        for(;j != AugPath.end();j++)
        {
            next = *j;
            if(GraphCapFlow[pre][next].cap == -1)
                GraphCapFlow[pre][next].flow -= bottleneck;
            else
                GraphCapFlow[pre][next].flow += bottleneck;
            pre = next;
        }

    #ifdef debug
        cout<<endl<<"updateFlow:"<<endl;
        cout<<"Numiterator: "<<Numiterator<<endl;
        cout<<"bottleneck: "<< bottleneck<<endl;
        for(int i = 0; i< Nodenum; i++){
        for(int j = 0; j<Nodenum; j++)
        {
        cout<<"("<<GraphCapFlow[i][j].cap<<","<<GraphCapFlow[i][j].flow<<")"<<": "<<ReGraphCapFlow[i][j]<<"  ";
        }
        cout<<endl;
    }

    #endif // debug
        return;
    }
    else if(n == 2)
    {
        GraphCapFlow[Source][Sink].flow =+ ReGraphCapFlow[Source][Sink];
        return;
    }
    else
        return;


}

void Graph::ChangeReflow(int& pre, int& next)
{
    if(GraphCapFlow[pre][next].flow<=GraphCapFlow[pre][next].cap)
    {
        ReGraphCapFlow[pre][next] = GraphCapFlow[pre][next].cap-GraphCapFlow[pre][next].flow;
    }
    if(GraphCapFlow[pre][next].flow > 0)
    {
        if(ReGraphCapFlow[next][pre] == -1) //There is no such path in Graph, so we such add this node to the Residual Graph.
        {
            node_t* pnode = new node_t;
            pnode->i = pre;
            pnode->next = pReGraphArray[next].next;
            pReGraphArray[next].next = pnode;
        }
        ReGraphCapFlow[next][pre] = GraphCapFlow[pre][next].flow;

    }
}

void Graph::ConReGraph()
{
    list<int>::iterator j = AugPath.begin();
    int pre, next;
    pre = AugPath.front();
    for(++j;j != AugPath.end();j++)
    {
        next = *j;
        ChangeReflow(pre, next);
        pre = next;
    }
    #ifdef debug
        cout<<endl<<"Residual Graph:"<<endl;
        for(int i = 0; i< Nodenum; i++){
        for(int j = 0; j<Nodenum; j++)
        {
        cout<<"("<<GraphCapFlow[i][j].cap<<","<<GraphCapFlow[i][j].flow<<")"<<": "<<ReGraphCapFlow[i][j]<<"  ";
        }
        cout<<endl;
    }

    #endif // debug
}

void Graph::mincut()
{
    int* NodeIndex = new int[Nodenum];
    for(int j = 0;j<Nodenum; j++)
        NodeIndex[j] = 0;
    queue<int> nodequeue;
    node_t anode; //= pReGraphArray[0];
    nodequeue.push(0);
    NodeIndex[0] = 1;
    while(!nodequeue.empty())
    {
        int nIndex = nodequeue.front();
        nodequeue.pop();
        anode = pReGraphArray[nIndex];
        while(anode.next != NULL )
        {
            if(NodeIndex[anode.next->i] == 1)
            {
                anode = *(anode.next);
                continue;
            }
            if(ReGraphCapFlow[pReGraphArray[nIndex].i][anode.next->i] == 0)
            {
                anode = *(anode.next);
                continue;
            }
            nodequeue.push(anode.next->i);
            NodeIndex[anode.next->i] = 1;
            anode = *(anode.next);
        }
    }
    outfile<<endl<<"Min-cut capacity = "<< maxflow<<endl;
    outfile<<"The min-cut is"<<endl;
    for(int k=0;k<Nodenum;k++)
    {
        if(NodeIndex[k] == 1)
            outfile<<k+1<<" ";
    }
    outfile<<endl;
    for(int k=0;k<Nodenum;k++)
    {
        if(NodeIndex[k] != 1)
            outfile<<k+1<<" ";
    }
    delete[] NodeIndex;
}

void Graph::FordFulkersonAlg()
{
    while(IsAugPath())//exist Augment Path, and using list save the path
    {
        UpdateFlow();
        ConReGraph();
    }
    outfile<<endl<<"Flow value = "<<maxflow<<endl;
    outfile<<"The max-flow is: "<<endl;
    node_t* pnode;
    for(int j = 0; j<Nodenum;j++)
    {
        if(pGraphArray[j].next == NULL)
            continue;
        pnode = pGraphArray[j].next;
        while(pnode != NULL)
        {
            outfile<<pGraphArray[j].i+1<<" "<<pnode->i+1<<" ";
            outfile<<GraphCapFlow[pGraphArray[j].i][pnode->i].flow<<endl;
            pnode = pnode->next;
        }
    }
    mincut();
    outfile.close();
}
